package com.xinwei.leetcode.栈;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Stack;

// https://leetcode-cn.com/problems/valid-parentheses/
public class _20_有效的括号 {
    /**
     * 判断的标准非常符合栈的逻辑：先进后出
     * 读到左括号就入栈，读到右括号则进行判断
     * 1、栈中为null，返回false
     * 2、栈顶括号不匹配，返回false
     * 3、栈顶括号匹配，继续遍历
     * 遍历完  栈中为null，则返回true  栈中还有值，则返回false
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{' || s.charAt(i) == '[' || s.charAt(i) == '(') {
                stack.push(s.charAt(i));
            }else {
                if (stack.size() == 0) return false;
                Character left = stack.pop();
                if ((s.charAt(i) == '}' && left != '{') || (s.charAt(i) == ']' && left != '[') ||
                        (s.charAt(i) == ')' && left != '(')){
                    return false;
                }
            }
        }
        // 这两句可以换成下面那个方法的一句
        if (stack.isEmpty()) return true;
        return false;
    }

    // 因为map适用于1对1的关系，所以可以一个key(左括号)对应一个value(右括号)
    public boolean isValid1(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(s.charAt(i))) {
                stack.push(s.charAt(i));
            }else {
                if (stack.size() == 0) return false;
                if (c != map.get(stack.pop())){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
